{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Kth Missing Positive Number"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findKthPositive"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #第 k 个缺失的正整数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个 <strong>严格升序排列</strong>&nbsp;的正整数数组 <code>arr</code>&nbsp;和一个整数&nbsp;<code>k</code>&nbsp;。</p>\n",
    "\n",
    "<p>请你找到这个数组里第&nbsp;<code>k</code>&nbsp;个缺失的正整数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [2,3,4,7,11], k = 5\n",
    "<strong>输出：</strong>9\n",
    "<strong>解释：</strong>缺失的正整数包括 [1,5,6,8,9,10,12,13,...] 。第 5 个缺失的正整数为 9 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [1,2,3,4], k = 2\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>缺失的正整数包括 [5,6,7,...] 。第 2 个缺失的正整数为 6 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= arr.length &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= arr[i] &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= 1000</code></li>\n",
    "\t<li>对于所有&nbsp;<code>1 &lt;= i &lt; j &lt;= arr.length</code>&nbsp;的 <code>i</code>&nbsp;和 <code>j</code> 满足&nbsp;<code>arr[i] &lt; arr[j]</code>&nbsp;</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong></p>\n",
    "\n",
    "<p>你可以设计一个时间复杂度小于 O(n) 的算法解决此问题吗？</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [kth-missing-positive-number](https://leetcode.cn/problems/kth-missing-positive-number/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [kth-missing-positive-number](https://leetcode.cn/problems/kth-missing-positive-number/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,3,4,7,11]\\n5', '[1,2,3,4]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "        ans = []\n",
    "        for i in range(10000):\n",
    "            if i not in arr:\n",
    "                res += 1\n",
    "                ans.append(i)\n",
    "                if res == k + 1:\n",
    "                    return ans[-1]\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        for i in arr:\n",
    "            if k < i:\n",
    "                return k\n",
    "            k += 1\n",
    "        return k\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        n = len(arr)\n",
    "        miss = [x - i - 1 for i, x in enumerate(arr)]\n",
    "        i = bisect_left(miss, k)\n",
    "        if i == n:\n",
    "            return k + n\n",
    "        return arr[i]-1-(miss[i]-k)\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        i = 1\n",
    "        while k > 0:\n",
    "            if i not in arr:\n",
    "                k -= 1\n",
    "            i += 1\n",
    "        return i - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        for i in arr:\n",
    "            if i<=k:\n",
    "                k+=1\n",
    "            else:\n",
    "                break\n",
    "        return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        if arr[0] > k:\n",
    "            return k\n",
    "        \n",
    "        l, r = 0,len(arr)\n",
    "        while l < r:\n",
    "            mid = (l + r) >> 1\n",
    "            x = arr[mid] if mid < len(arr) else 10 ** 9\n",
    "            if x - mid - 1 >= k:\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return k - (arr[l - 1] - (l - 1) - 1) + arr[l - 1]\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        arr.insert(0, 0)\n",
    "        left, right = 0, len(arr)-1\n",
    "        while left<=right:\n",
    "            mid = left + (right-left)//2\n",
    "            temp = arr[mid]-mid\n",
    "            if temp >= k:\n",
    "                right = mid-1\n",
    "            else:\n",
    "                left = mid+1\n",
    "\n",
    "        return k+right\n",
    "        \"\"\"\n",
    "        x = 0\n",
    "        for i in range(1, arr[-1]):\n",
    "            if i not in arr:\n",
    "                x += 1\n",
    "                if x == k:\n",
    "                    return i\n",
    "        if x < k:\n",
    "            return arr[-1] + (k - x)\n",
    "        \"\"\"\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        n = len(arr)\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            if arr[i] - i - 1 >= k:\n",
    "                return k + i\n",
    "            i += 1\n",
    "        return k + i\n",
    "\n",
    "\n",
    "# 解法1：暴力解法\n",
    "# 首先最容易想到的莫过于暴力解法，由于1 <= arr[i] <= 1000,1 <= k <= 1000,\n",
    "# 因而返回的答案不超过2000，不妨把数组开大一些，然后扫描arr，\n",
    "# 将所有这些出现的元素标记为-1,最后查找第K个不等于-1的元素即可。\n",
    "\n",
    "# O(0)\n",
    "# class Solution:\n",
    "#     def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "#         nums = [0] * 2000\n",
    "#         for i in arr:\n",
    "#             nums[i - 1] = -1\n",
    "#         # print(nums)\n",
    "#         for i in range(len(nums)):\n",
    "#             if nums[i] == 0:\n",
    "#                 k -= 1\n",
    "#             if k == 0:\n",
    "#                 return i + 1\n",
    "#         return 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        missCount=0\n",
    "        lastMiss =-1\n",
    "        current=1\n",
    "        ptr=0\n",
    "\n",
    "        while missCount<k:\n",
    "            if current == arr[ptr]:\n",
    "                if ptr+1 < len(arr):\n",
    "                    ptr +=1\n",
    "            else:\n",
    "                missCount +=1\n",
    "                lastMiss=current\n",
    "            current +=1\n",
    "        return lastMiss\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        for v in arr:\n",
    "            if v<=k:\n",
    "                k+=1\n",
    "        return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        x = 0\n",
    "        for i in arr:\n",
    "            x += 1\n",
    "            if i == x:\n",
    "                continue\n",
    "            else:\n",
    "                while i != x:\n",
    "                    k -= 1\n",
    "                    if k == 0:\n",
    "                        return x\n",
    "                    x += 1\n",
    "        return k + x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        count = 0\n",
    "        num = 1\n",
    "        while True:\n",
    "            if num not in arr:\n",
    "                count+=1\n",
    "                if count == k:\n",
    "                    return num\n",
    "            num+=1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        nums = list(range(1, len(arr)+k+1))\n",
    "        for i in arr:\n",
    "            if i in nums:\n",
    "                nums.remove(i)\n",
    "        return nums[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        flag = 0\n",
    "        for i in range(1,5000):\n",
    "            if i not in arr:\n",
    "                flag += 1\n",
    "            if (flag==k):\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        if arr[0] > k:\n",
    "            print(k)\n",
    "            return k\n",
    "\n",
    "        left = 0\n",
    "        right = len(arr)\n",
    "\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            diff = arr[mid] - mid - 1\n",
    "            if k > diff:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "            # elif k < diff:\n",
    "            #     right = mid\n",
    "            # else:\n",
    "            #     print(arr[mid] - diff)\n",
    "            #     return arr[mid] - diff\n",
    "\n",
    "        # print(left)\n",
    "        # print(right)\n",
    "\n",
    "        print(k - (arr[left - 1] - (left - 1) - 1) + arr[left - 1])\n",
    "        return k - (arr[left - 1] - (left - 1) - 1) + arr[left - 1]\n",
    "        mid = (left - 1) if (left == len(arr)) else left\n",
    "        # mid = -1\n",
    "        # if left == len(arr):\n",
    "        #     mid = left\n",
    "        # else:\n",
    "        #     mid = left\n",
    "        diff = arr[left] - (left + 1)\n",
    "        k = k - diff\n",
    "        print(arr[left] + k)\n",
    "        # if left == len(arr):\n",
    "        #     mid = left - 1\n",
    "        #     diff = arr[mid] - (mid + 1)\n",
    "        #     k = k - diff\n",
    "        #     print(arr[mid] + k)\n",
    "        # else:\n",
    "        #     mid = left\n",
    "\n",
    "        #\n",
    "        # if left == 0:\n",
    "        #     mid = 0\n",
    "\n",
    "            # diff = arr[mid] - (mid + 1)\n",
    "            # k = k - diff\n",
    "            # print(arr[mid] - k)\n",
    "\n",
    "        # k = 5\n",
    "        # 0 1 2 3 4\n",
    "        # 2 3 4 7 11\n",
    "        # mid = 2\n",
    "        # diff = 1\n",
    "        #\n",
    "        #\n",
    "        # 0 1 2 3\n",
    "        # 1 2 3 4\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    arr = [1, 2, 3, 4]\n",
    "    k = 2\n",
    "\n",
    "    # arr = [4, 6, 9]\n",
    "    # k = 1\n",
    "\n",
    "    # arr = [2,3,4,7,11]\n",
    "    # k = 5\n",
    "\n",
    "\n",
    "\n",
    "    s = Solution()\n",
    "    s.findKthPositive(arr, k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        miss = [x - i - 1 for i, x in enumerate(arr)]\n",
    "        i = bisect_left(miss, k)\n",
    "        return k + i\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr, k) :\n",
    "        mid = []\n",
    "        res = []\n",
    "        for idx in range(arr[-1]):\n",
    "            mid.append(idx+1)\n",
    "        i = 0\n",
    "        j = 0\n",
    "        for value in arr:\n",
    "            while value != mid[j]:\n",
    "                res.append(mid[j])\n",
    "                j += 1\n",
    "            j += 1\n",
    "        if k > len(res):\n",
    "            res.append(arr[-1] + k - len(res))\n",
    "            return res[-1]\n",
    "        else:\n",
    "            return res[k - 1]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        temp = 0\n",
    "        if arr[0]>1:\n",
    "            if k>arr[0]-1:\n",
    "                k -= arr[0]-1\n",
    "            else:\n",
    "                for i in range(k):\n",
    "                    temp += 1\n",
    "                return temp\n",
    "        for i in range(1,len(arr)):\n",
    "            if arr[i]-arr[i-1]-1 < k:\n",
    "                k -= arr[i]-arr[i-1]-1\n",
    "            else:\n",
    "                for _ in range(k):\n",
    "                    arr[i-1] += 1\n",
    "                return arr[i-1]\n",
    "        for i in range(k):\n",
    "            arr[-1] += 1\n",
    "        return arr[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        length = len(arr)\n",
    "        a, b = 0, length - 1\n",
    "        if arr[b] - b - 1 < k:\n",
    "            return b + k + 1\n",
    "        elif arr[a] > k:\n",
    "            return k\n",
    "        while a < b:\n",
    "            c = a + (b - a) // 2\n",
    "            remain = arr[c] - c - 1\n",
    "            if remain >= k:\n",
    "                b = c\n",
    "            else:\n",
    "                a = c + 1\n",
    "        return b + k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        arr.insert(0, 0)\n",
    "        for i in range(1, len(arr)):\n",
    "            diff = arr[i] - arr[i-1] - 1\n",
    "            if diff > 0:\n",
    "                k -= diff\n",
    "                if k <= 0:\n",
    "                    return arr[i] + k - 1\n",
    "        return arr[i] + k\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "         for i, val in enumerate(arr):\n",
    "            if k < val:\n",
    "                return k\n",
    "            else:\n",
    "                k += 1\n",
    "\n",
    "         return k\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        for i in arr:\n",
    "            if i > k:\n",
    "                break\n",
    "            k += 1\n",
    "\n",
    "        return k\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        # return sorted(set(list(range(1, max(arr)+k+1))) - set(arr))[k-1]\n",
    "        n = list(range(1, max(arr)+k+1))\n",
    "        for i in arr:\n",
    "            n.remove(i)\n",
    "        return n[k-1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        for i,num in enumerate(arr):\n",
    "            if num-i-1 >= k:\n",
    "                break\n",
    "        if num-i-1 < k:\n",
    "            return k+i+1\n",
    "        else:\n",
    "            return k+i                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        cnt = 0\n",
    "        for i in range(1, max(arr)):\n",
    "            if i not in arr:\n",
    "                cnt += 1\n",
    "                if cnt == k:\n",
    "                    return i\n",
    "\n",
    "        if cnt < k:\n",
    "            return arr[-1] + k - cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        miss_count = 0\n",
    "        last_miss = -1\n",
    "\n",
    "        current = 1\n",
    "\n",
    "        ptr = 0\n",
    "\n",
    "        while miss_count < k:\n",
    "            if current == arr[ptr]:\n",
    "                if ptr + 1 < len(arr):\n",
    "                    ptr += 1\n",
    "            else:\n",
    "                miss_count += 1\n",
    "                last_miss = current\n",
    "            current +=1\n",
    "        return last_miss"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        missCount = 0\n",
    "        lastMiss = -1\n",
    "        current = 1\n",
    "        ptr = 0\n",
    "\n",
    "        while missCount < k:\n",
    "            if current == arr[ptr]:\n",
    "                if ptr + 1 < len(arr):\n",
    "                    ptr += 1\n",
    "            else:\n",
    "                missCount += 1\n",
    "                lastMiss = current\n",
    "            current += 1\n",
    "        \n",
    "        return lastMiss\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        count = 0\n",
    "        for i in range(1,k+1+len(arr)):\n",
    "            if i not in arr:\n",
    "                count = count+1\n",
    "                if count==k:\n",
    "                    return i\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        if arr[0] != 1:  # 统计一开始缺失的\n",
    "            if arr[0] - 1 >= k:\n",
    "                return 1 + k - 1\n",
    "            k -= arr[0] - 1\n",
    "        for i in range(1, len(arr)):\n",
    "            diff = arr[i] - arr[i - 1] - 1\n",
    "            if k <= diff:\n",
    "                return arr[i - 1] + k\n",
    "            k -= diff\n",
    "        return arr[-1] + k\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        new=[i for i in range(1,arr[-1]+k+1) if i not in arr]\n",
    "        return new[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        left, right = 0, len(arr) - 1\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if arr[mid] - mid - 1 >= k:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left + k\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 思路就是遍历整个障碍数组，根据提示，障碍数组是按照顺序排序的，我每次都假设现在可以返回k了，但是如果k >= val,那我就跳过当前的值，同时k = k+1， 如果 k < val,那么就直接返回k。\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        for i in arr:\n",
    "            if k < i:\n",
    "                break\n",
    "            k += 1\n",
    "        return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        misscount = 0\n",
    "        current = 1\n",
    "        index = 0\n",
    "        lastmiss= -1\n",
    "        while misscount < k:\n",
    "            if current == arr[index]:\n",
    "                if index < len(arr) - 1:\n",
    "                    index += 1\n",
    "            else:\n",
    "                lastmiss = current\n",
    "                misscount += 1\n",
    "            current += 1\n",
    "        return lastmiss\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        cnt = 0\n",
    "        i = 1\n",
    "        while True:\n",
    "            if i not in arr:\n",
    "                cnt += 1\n",
    "            if cnt == k:\n",
    "                return i\n",
    "            i += 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        cnt = 0\n",
    "        for i in range(1, max(arr)):\n",
    "            if i not in arr:\n",
    "                cnt += 1\n",
    "                if cnt == k:\n",
    "                    return i\n",
    "\n",
    "        if cnt < k:\n",
    "            return arr[-1] + k - cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        a,lost = 0,0 \n",
    "        for n in range(1,2000):  # 题目给出的最大循环次数=最大arr元素数量+最大k\n",
    "            if n != arr[a]:   # arr[a]不等于n\n",
    "                lost +=1      # lost记录丢失了多少个正整数\n",
    "                if lost == k: return n  # lost达到k则返回当前n\n",
    "            else: # arr[a]等于n\n",
    "                if a<len(arr)-1: a +=1  # arr还有元素，继续遍历\n",
    "                else: return n+(k-lost) # arr已经没有元素，通过n+(k-lost)计算出丢失的第k个正整数\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        n = len(arr)\n",
    "        if arr[0] > k:\n",
    "            return k\n",
    "\n",
    "        left = 0\n",
    "        right = n - 1\n",
    "        while left <= right:\n",
    "            print(left)\n",
    "            print(right)\n",
    "            mid = (left + right)//2\n",
    "            if arr[mid] - mid - 1 >= k:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return arr[right] + k - (arr[right] - (right) - 1) if k - (arr[right] - (right) - 1) > 0 else arr[right - 1] + k - (arr[right - 1] - (right - 1) - 1)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        arr.insert(0, 0)\n",
    "        left, right = 0, len(arr)-1\n",
    "        while left<=right:\n",
    "            mid = left + (right-left)//2\n",
    "            temp = arr[mid]-mid\n",
    "            if temp >= k:\n",
    "                right = mid-1\n",
    "            else:\n",
    "                left = mid+1\n",
    "\n",
    "        return k+right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        nums = list(range(1, len(arr)+k+1))\n",
    "        return sorted(set(nums) - set(arr))[k-1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        s = set(arr)\n",
    "        c = 0\n",
    "        for i in range(1, arr[-1] + 1):\n",
    "            if i not in s:\n",
    "                c += 1\n",
    "            if c == k:\n",
    "                return i\n",
    "        return arr[-1] + k - c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        for i in range(1, 10000):\n",
    "            if i not in arr:\n",
    "                k-=1\n",
    "            if not k:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        lst=[i for i in range (1,max(arr)+k+1) if i not in arr]\n",
    "        return lst[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        start, end = 0, len(arr) - 1\n",
    "        mid = (start + end) >> 1\n",
    "        while start <= end:\n",
    "            c = arr[mid] - mid - 1\n",
    "            if c < k:\n",
    "                start = mid + 1\n",
    "            else:\n",
    "                end = mid - 1\n",
    "            mid = (start + end) >> 1\n",
    "        return start + k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        l = 0\n",
    "        r = len(arr)\n",
    "        while l < r:\n",
    "            mid = (l+r) // 2\n",
    "            if arr[mid] - mid - 1 >= k:\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l + k\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        nums = [i for i in range(1,1001+k) if i not in arr]\n",
    "        return nums[k-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        nums = list(range(1, len(arr)+k+1))\n",
    "        diff = sorted(set(nums) - set(arr))\n",
    "        return diff[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        \"\"\"\n",
    "        利用下标和元素的关系第i个元素arr[i]-i-1就是到现在缺失的元素个数\n",
    "        因此可以采用二分查找\n",
    "        \"\"\"\n",
    "        left = 0\n",
    "        right = len(arr)\n",
    "        while left<right:\n",
    "            mid = (left+right)//2\n",
    "            if arr[mid]-mid>=k+1:#当前元素缺失更多 \n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid+1\n",
    "        return left + k\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        i = 1\n",
    "        li = []\n",
    "        ma = arr[-1]\n",
    "        while i != ma+k+1:\n",
    "            if len(arr) == 0 or i != arr[0]:\n",
    "                li.append(i)  \n",
    "            else:\n",
    "                del arr[0]\n",
    "            if len(li) == k:\n",
    "                return li[-1]\n",
    "            i += 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        count = 0\n",
    "        index = 0\n",
    "        arr = arr+[None]*k\n",
    "        for i in range(1,k+1+len(arr)):\n",
    "            if i != arr[index]:\n",
    "                count = count+1\n",
    "                if count==k:\n",
    "                    return i\n",
    "            else:\n",
    "                index = index+1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        nums = [0] * 2100\n",
    "        for i in arr:\n",
    "            nums[i] = i\n",
    "        \n",
    "        cnt = 0\n",
    "        for j in range(1, len(nums)):\n",
    "            if nums[j] == 0:\n",
    "                cnt += 1\n",
    "                if cnt == k:\n",
    "                    return j\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        mark = arr[0] - 1\n",
    "        if mark >= k:\n",
    "            return k\n",
    "        for i in range(len(arr)-1):\n",
    "            if mark + arr[i+1]-arr[i]-1 >= k:\n",
    "                print(mark,'最后一次mark')\n",
    "                return arr[i]+k-mark\n",
    "            mark += arr[i+1]-arr[i]-1\n",
    "        return arr[-1]+k-mark\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        for i in range(len(arr)):\n",
    "            if arr[i] <= k :\n",
    "                k += 1\n",
    "        return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        m = 0\n",
    "        n = 0\n",
    "        while m < k:\n",
    "            n += 1\n",
    "            if n not in arr:\n",
    "                m += 1\n",
    "\n",
    "        return n "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        if k < arr[0]:\n",
    "            return k\n",
    "        k -= arr[0] - 1\n",
    "        for i in range(len(arr)):\n",
    "            if i == len(arr) - 1 or arr[i] + k < arr[i+1]:\n",
    "                return arr[i] + k\n",
    "            k -= arr[i+1] - arr[i] - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        l=0\n",
    "        r=len(arr)-1\n",
    "        while l<r:\n",
    "            m=l+(r-l)//2\n",
    "            p=arr[m]-m-1\n",
    "            if p>=k:\n",
    "                r=m\n",
    "            else:\n",
    "                l=m+1\n",
    "        p=arr[l]-l-1\n",
    "        if p>=k:\n",
    "            return l+k\n",
    "        else:\n",
    "            return l+k+1     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        length = len(arr)\n",
    "        \n",
    "        left = 0\n",
    "        right = length - 1\n",
    "\n",
    "        find = length\n",
    "\n",
    "        while left <= right:\n",
    "            \n",
    "            mid = (left + right) // 2\n",
    "\n",
    "            if arr[mid] - mid - 1 >= k:\n",
    "                find = mid\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        \n",
    "        prev_value = 0 if find == 0 else arr[find - 1]\n",
    "        under = prev_value -  find\n",
    "        return prev_value + (k-under)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        '''\n",
    "        a=max(arr)+k+1\n",
    "        lst=[i for i in range (1,a) if i not in arr]\n",
    "        return lst[k-1]\n",
    "        '''\n",
    "        n=len(arr)\n",
    "        lst=[]\n",
    "        if n==1:\n",
    "            return k if k<arr[0] else k+1\n",
    "        for i in range(n):\n",
    "            lst.append(arr[i]-i-1)\n",
    "        if k>lst[-1]:\n",
    "            return arr[-1]+k-lst[-1]\n",
    "        elif k<=lst[0]:\n",
    "            return k\n",
    "        else:\n",
    "            for i in range(n-1):\n",
    "                if lst[i]<k<=lst[i+1]:\n",
    "                    return arr[i]+k-lst[i]\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        # missCount = 0\n",
    "        # lastMiss = -1\n",
    "        # current = 1\n",
    "        # ptr = 0\n",
    "\n",
    "        # while missCount < k:\n",
    "        #     if current == arr[ptr]:\n",
    "        #         if ptr + 1 < len(arr):\n",
    "        #             ptr += 1\n",
    "        #     else:\n",
    "        #         missCount += 1\n",
    "        #         lastMiss = current\n",
    "        #     current += 1\n",
    "        \n",
    "        # return lastMiss\n",
    "        # missCount = 0\n",
    "        # curr = 1\n",
    "        # lastmiss = -1\n",
    "        # ptr = 0\n",
    "        # while missCount <k:\n",
    "        #     if curr == arr[ptr]:\n",
    "        #         if ptr+1 < len(arr):\n",
    "        #             ptr += 1\n",
    "        #     else:\n",
    "        #         missCount +=1\n",
    "        #         lastMiss = curr\n",
    "        #     curr += 1\n",
    "        curr = 1\n",
    "        missCount = 0\n",
    "        lastMiss = -1\n",
    "        ptr = 0\n",
    "\n",
    "        while missCount < k:\n",
    "            if curr == arr[ptr]:\n",
    "                if ptr+1 <len(arr):\n",
    "                    ptr += 1\n",
    "\n",
    "            else:\n",
    "                missCount +=1\n",
    "                lastMiss = curr\n",
    "            curr += 1\n",
    "        return lastMiss"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        nums = [0] * 2300\n",
    "        for i in arr:\n",
    "            nums[i] = i\n",
    "        \n",
    "        cnt = 0\n",
    "        for j in range(1, len(nums)):\n",
    "            if nums[j] == 0:\n",
    "                cnt += 1\n",
    "                if cnt == k:\n",
    "                    return j\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        nums = [0] * 5000\n",
    "        for i in arr:\n",
    "            nums[i] = i\n",
    "        \n",
    "        cnt = 0\n",
    "        for j in range(1, len(nums)):\n",
    "            if nums[j] == 0:\n",
    "                cnt += 1\n",
    "                if cnt == k:\n",
    "                    return j\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        nums = [0] * 5000\n",
    "        for i in arr:\n",
    "            nums[i] = i\n",
    "        \n",
    "        cnt = 0\n",
    "        for j in range(1, len(nums)):\n",
    "            if nums[j] == 0:\n",
    "                cnt += 1\n",
    "                if cnt == k:\n",
    "                    return j\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        m = 0\n",
    "        n = 0\n",
    "        while m < k:\n",
    "            n += 1\n",
    "            if n not in arr:\n",
    "                m += 1\n",
    "\n",
    "        return n "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        nums = [0 for _ in range(3000)]\n",
    "        for i in arr:\n",
    "            nums[i] = i\n",
    "        \n",
    "        cnt = 0\n",
    "        for j in range(1, len(nums)):\n",
    "            if nums[j] == 0:\n",
    "                cnt += 1\n",
    "                if cnt == k:\n",
    "                    return j\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        return sorted(set(list(range(1, len(arr)+k+1))) - set(arr))[k-1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        b=[]\n",
    "        for i in range(1,arr[-1]*4):\n",
    "            b.append(i)\n",
    "        c=[]\n",
    "        for i in b:\n",
    "            if i not in arr:\n",
    "                c.append(i)\n",
    "        if len(c)==0:\n",
    "            return arr[-1]+k\n",
    "        else:\n",
    "            return c[k - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        arr.insert(0, 0)\n",
    "        left, right = 0, len(arr)-1\n",
    "        while left<=right:\n",
    "            mid = (right+left)//2\n",
    "            temp = arr[mid]-mid\n",
    "            if temp >= k:\n",
    "                right = mid-1\n",
    "            else:\n",
    "                left = mid+1\n",
    "\n",
    "        return k+right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        return sorted(set(range(1,max(arr) + k + 1)) - set(arr))[k-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        a=[i for i in range(1,max(arr)+k+1)]\n",
    "        b=0\n",
    "        for i in a:\n",
    "            if b!=k:\n",
    "                if i not in arr:\n",
    "                    b+=1\n",
    "                    if b==k:\n",
    "                        return i\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\n",
    "        return list(set([i for i in range(1, 3001)]) - set(arr))[k - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findKthPositive(self, arr: List[int], k: int) -> int:\r\n",
    "        tmp = [0] * (arr[-1] + k)\r\n",
    "        res = []\r\n",
    "        for i in arr:\r\n",
    "            tmp[i - 1] += 1\r\n",
    "        for j in range(len(tmp)):\r\n",
    "            if tmp[j] == 0:\r\n",
    "                res.append(j + 1)\r\n",
    "        return res[k - 1]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
